COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂15-Aug-82  1003	PWEGNER at BBNA
C00005 00003	Peter and Simon:
C00011 00004	∂16-Aug-82  1846	PWEGNER at BBNA
C00017 ENDMK
C⊗;
∂15-Aug-82  1003	PWEGNER at BBNA
Date: 15 Aug 1982 1302-EDT
Sender: PWEGNER at BBNA
From: PWEGNER at BBNA
To: JMC at SU-AI
Message-ID: <[BBNA]15-Aug-82 13:02:17.PWEGNER>
In-Reply-To: Your message of 13 Aug 1982 2246-PDT

Simon and I enjoyed your result and rapidly discovered that it did
not generalize to the 10 queens case.
In the 10 queens case the first solution has (1,1) (2,3) and (3,6)
in the first three columns.
Perhaps it could be shown that (1,1) (2,3) and (3,5) is impossible using your
techniques.

We have made the following experimental discoveries.
1. The number of toroidal solutions for N = 5,7,11 is respectively 10,28,88.
We conjecture that for N prime the number of solutions is N (N-3).
Note that this follows from the conjecture that there are no non-linear
solutions for N prime.
This result would mean that the number of solutions increases only quadratically
rather than exponentially for N prime.
It would be nice to explore solutions for non prime values of N, but the 
smallest such value (N=25) is too large for us to try.
Perhaps the number of solutions for all N increases only
polinomially in the toroidal case?
Even if it is exponential, the coefficient of the exponential term is
miniscule.

2. Startin with center columns and moving outwards to edge columns makes
no difference (non-toroidal case).
We are working on trying columns based on the smallest number of safe rows,
and hope to have it implemented soon.

The idea of implementing something with checking on number of available
diagonals sounds interesting.
Will think about it some more.

Will keep you posted on developments
	peter

Peter and Simon:
	In testing your conjecture, you stopped just too soon.  The
paper by Bruen and Dixon cited in the literature search you have
shows how to construct a class of  non-linear solutions for
all  p > 11.  You are right that the argument I gave for
((1,1),(2,3)) has little generality.  It also doesn't work out
nicely for  ((1,1),(2,4)), i.e. much more
case analysis seems to be required.  I have written a Lisp program,
but I don't know if I'll have time to enter it and test it today.
Most of the papers concern programming methodology, and a first
look suggests that considering programming methodology puts blinkers
on a programmer so he doesn't think about better algorithms.
It would be interesting to challenge Dijkstra or Wirth or
McKeeman or Naur or Cohen to modify his program to count
available diagonals (which I believe will reduce search
more than enough to pay its freight at least when  N  is large),
and see if anything is left of the original program.
I forgot to say that there is a large class of almost linear solutions


for the non-toroidal case.  Starting with  ((
((1,2),(2,4)), continuing by knight's moves to the top, then
proceeding to the bottom of the next column and continuing up
by knights moves works when  N == 0,4 mod 6.  Since
it avoids a long diagonal it extends to solutions for
N == 1,5 mod 6.  N ==  2 mod 6  is
harder, but the  result of starting in   (1,1)
and proceeding linearly by knight's moves, which fails to be a
solution, because it uses the main diagonal twice, can be modified
by shifting the 4th queen all the way to the right and pulling
the top queen back to its row.  This works for  N ==  2 mod 6
except for  N = 8.
It was conjectured that there are systematic reasons why many
configurations of the n-queens problem fail to yield solutions
in the subsequent search.  Here is a preliminary result proving
that putting queens in positions (1,1) and (2,3) cannot lead
to a solution.  First note that wee must put a queen in the
second row, I don't care where.  Next note that the squares
not already excluded form two triangles containing 8 diagonals.
(Some squares from these triangles will be ecluded depending
on the location of the queen in row 2, but we don't need to
worry about which they are, because the configuration
would lose if none were excluded except row 2 itself).
A simple analysis of the 4 diagonals of each triangle shows
that at most  2  of the diagonals can contain queens.
This places at most 4 queens, and there are 5 to go.

The idea of this proof is that while there are initially
2n-1 diagonals of positive slope and 2n-1 of negative
slope, they are rapidly knocked off by placing queens for
two reasons.  Placing each queen occupies a diagonal, but
also diagonals are eliminated by eliminating all their squares
as being attacked.  Whenever there are fewer available diagonals
 of one slope than queens to be
placed, the search can stop without worrying about where
the queens go in the diagonals.  I should have said that
the above paragraph used only diagonals of positive slope.

It might be quite a challenge to write a program that
counted available diagonals and their mutual exclusions
in order to reduce search, but it seems clear that


vast reductions are possible in the number of positions
examined.

More later if discovered, but I send this hoping you and
Simon will get some results along this line.  Of course,
there may be some possibility that more number theory will
get still more powerful results.

I looked at all the papers that Dialog turned
up that were in the IBM library.  None gave any hint that 
straightforward backtracking plus symmetry could be improved
upon.
∂16-Aug-82  1846	PWEGNER at BBNA
Date: 16 Aug 1982 2144-EDT
Sender: PWEGNER at BBNA
From: PWEGNER at BBNA
To: JMC at SU-AI
Message-ID: <[BBNA]16-Aug-82 21:44:20.PWEGNER>
In-Reply-To: Your message of 15 Aug 1982 1053-PDT

John
	Here are some more experimental results.

There are an abundance of non-linear solutions for N = 13.
In particular there are 35 non-linear solutions between the first and second
of the 130 linear solutions.

Placing queens in the column with the minimum number of safe rows decreases
the number of queen placements for the regular eight queens problem from
2056 to 1305.
This is for the complete set of 92 solutions.

Since the number of solutions appears to be exponential in both the toroidal and
the non-toroidal case, the total amount of work to find all solutions is exponential.
I suppose that the measure of work we are ying to reduce is the average
number of queen placements per solution.
But there is little consolation in reducing this if it is irreducably exponential.

With regard to programming methodology, we started with a Wirth-like program
in Pascal and found it easy to generalize to the non-toroidal and minimum 
in column case.
However you are probably right in conjecturing that emphasis on methodology
may have inhibited consideration
of generalizations and better backtracking strategies.
Lisp may well be better than Pascal in searching for patterns which cannot
be completed into a solution.
But the hard part is finding systematic heuristics.
	peter

More on n queens

	While I was on the trip and had no access to a computer, I
experimented with the  n  queens problem and found another heuristic
that cuts down the search to the extent that all solutions
of the 8 queens problem were found found with less than 100 backtracks.
The key point is to find ways to eliminate squares from consideration
and to eliminate enough squares so that a square that must be in any
further solution can be found.  The resources method that I found for
((1 1) (1 3)) is not often applicable although I found more occasion
for it in 10 queens with which I also experimented, getting all the
solutions following  ((1 1) (1 3)).  The new method of eliminating
squares is to find a square that sees all unoccupied squares in a row
or column (or necessary diagonal or other necessary set more rarely).
Such a square cannot have a queen on it.  In most positions after 3
queens have been placed on the 8 queen board, such squares can be
found.  Since eliminating some of these squares reduces the number
in a row or column, this may make it possible to eliminate more
squares.  If all squares in an essential set are eliminated, there
is no solution, and if all but one are eliminated a queen may be
placed that won't cause backtracking.  Sometimes backtracking has
to be carried to the placing of 4 or even 5 queens, but usually 3
suffice.  It is important also to remember that one can switch
from scanning a row to scanning a column and vice versa at any time without
risking the loss of solutions.  Also I used symmetry very heavily.
Namely, one can eliminate any position that contains as a subset
a position that is isomorphic to a position all of whose continuations
have been studied.  Thus after all the continuations of  ((1 1)) have
been studied, the corner squares can be removed from the board.

	In my opinion, with these heuristics a program on a micro
computer might beat a program on a Cray on large boards.